#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next


class Solution:
    """
    @param head: n
    @return: The new head of reversed linked list.
    """
    def reverse(self, head):
        # return self.non_rec_reverse1(head)
        # return self.non_rec_reverse2(head)

        if not head or not head.next:
            return head

        new_head, new_tail = self.rec_reverse(head)
        new_tail.next = None
        return new_head


    def rec_reverse(self, node):
        # 相当于由系统维护一个stack: 把元素先放入stack中, 再倒过来.
        # 如果算上函数stack: space complexity为 O(n)
        if not node or not node.next:
            return node, node

        new_node, new_tail = self.rec_reverse(node.next)
        # new_tail.next = None
        new_tail.next = node
        return new_node, node

    def non_rec_reverse1(self, head):
        # 循环遍历: 把指针方向扭转
        # 1 ---> 2 ----> 3
        # 1 <--- 2 <---- 3
        pre, cur = None, head

        while cur:
            # save
            next = cur.next

            # update: pivot
            cur.next = pre

            # drive loop
            pre, cur = cur, next

        return pre

    def non_rec_reverse2(self, node):
        # 每次去除一个元素来放在新的头部
        if not node:
            return node
        head = node
        node = node.next
        head.next = None

        while node:
            node_save = node
            node = node.next
            node_save.next = head
            head = node_save

        return head


def test():
    pass

def show(n):
    while n:
        print("%s ----> " % n.val, sep=' ', end=' ')
        n = n.next
    print()

def main():
    print("start main")

    v5 = ListNode(5)
    v4 = ListNode(4, v5)
    v3 = ListNode(10, v4)
    v2 = ListNode(2, v3)
    v1 = ListNode(2, v2)
    v0 = ListNode(2, v1)
    vm = ListNode(100, v0)
    show(vm)

    s = Solution()
    ret = s.reverse(vm)
    show(ret)

if __name__ == "__main__":
    main()
